Ông quê Thôn Đông, xã Đoàn Tùng (sau đổi là Đoàn Lâm), huyện Trường Tân, phủ Hạ Hồng, trấn Hải Dương (nay là Thanh Tùng, huyện Thanh Miện, tỉnh Hải Dương),

Đời vua Lê Nhân Tông, niên hiệu Thái Hòa 11 (năm 1453), ông thi đậu Đệ nhị giáp tiến sĩ xuất thân (Hoàng Giáp), khoa Quý Dậu, năm 20 tuổi, được vua phong chức quan Hàn lâm kiêm Vương phó (thầy dạy học cho các vương tử). Vốn thông minh, tài đối đáp, ông được vua Lê Thánh Tông giao cho ba lần đi sứ nhà Minh.

Khi làm quan ông dốc lòng vì công việc, dù ở cương vị Đô lý tự khanh tra xét các vụ kiện, Vương phó, tham nghị binh chính hay Quan ty cẩm y vệ, cũng hoàn thành tốt nhiệm vụ được giao, được các quan trong triều kính trọng, nể phục.

Khi vua Lê Thánh Tông đem quân đi đánh Chiêm Thành, Nguyễn Phục giữ chức Đô Chỉ Huy Sứ đốc vận chuyển quân nhu. Khi xuất phát đi tiếp tế quân lương gặp bão lớn, ông quyết định chờ tan bão mới đi, thuyền quân lương bị chậm vài ngày. Quân luật khép ông vào tội bất tuân quân lệnh, bị xử tội chém.